#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
    int shipWithinDays(std::vector<int>& weights, int days) {
        int maxWeight = 0;
        for (std::vector<int>::iterator it = weights.begin(); it != weights.end(); ++it) {
            if (*it > maxWeight) {
                maxWeight = *it;
            }
        }
        int totalWeight = 0;
        for (std::vector<int>::iterator it = weights.begin(); it != weights.end(); ++it) {
            totalWeight += *it;
        }
        int left = maxWeight;
        int right = totalWeight;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int temp = mid;
            int time = 1;
            for (std::vector<int>::iterator it = weights.begin(); it != weights.end(); ++it) {
                if (temp >= *it) {
                    temp -= *it;
                } else {
                    temp = mid - *it;
                    time++;
                }
            }
            if (time > days) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};
int main() {
    Solution sol;
    std::vector<int> weights;
    weights.push_back(1);
    weights.push_back(2);
    weights.push_back(3);
    weights.push_back(4);
    weights.push_back(5);
    weights.push_back(6);
    weights.push_back(7);
    weights.push_back(8);
    weights.push_back(9);
    weights.push_back(10);
    int days = 5;
    int result = sol.shipWithinDays(weights, days);
    std::cout << "The minimum ship capacity needed is: " << result << std::endl;
    return 0;
}

